package cn.edu.xjtu.work.findMedianSortedArrays;

/**
 * 4. 寻找两个正序数组的中位数
 * 
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 */
public class Solution {
  public static void main(String[] args) {
    // int[] nums1 = { 1, 3 };
    int[] nums1 = {};
    int[] nums2 = { 2 };
    System.out.println(findMedianSortedArrays(nums1, nums2));

  }

  /**
   * 返回两个数组的中位数
   * 
   * 首先考虑如何将偶数和奇数的情况合并,由于不论是偶数还是奇数都需要遍历(m+n)/2+1次,
   * 奇数直接取最后一次的结果返回,偶数则需找到上一位求平均值返回,因此只需要再多一个变量存储上一位的值就行
   * 
   * 判断的思路是首先考虑right可以取到nums1数组当前元素的情况,该情况首先nums1肯定没有取到最后一个元素
   * 然后分两种情况,要么nums2数组取到了最后一个元素,要么nums2当前元素的值小于nums1当前元素的值
   * 此时可直接令right取nums1当前元素的值,其余情况right均取nums2当前的元素
   * 
   * 最后返回的时候分奇数偶数返回即可
   * 
   * @param nums1 数组1
   * @param nums2 数组2
   * @return 中位数
   */
  public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;

    double left = 0, right = 0;
    int aStart = 0, bStart = 0;

    for (int i = 0; i < (m + n) / 2 + 1; i++) {
      left = right;
      if (aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {
        right = nums1[aStart++];
      } else {
        right = nums2[bStart++];
      }
    }

    if ((m + n) % 2 == 0) {
      return (left + right) / 2;
    } else {
      return right;
    }

  }
}
